수열의 귀납적 정의와 점화식
점화식 an+1 = pan + q . . . ①, a1 = a . . . ②를 만족하는 수열 {an}의 일반항은
(1) p = 1일 때 an = a + (n-1)q . . . ③
(2) p ≠ 1일 때 an = pn-1(a -) +
. . . ④
수열 {an}에 대해 위의 두 규칙 ①과 ②가 주어지면 ②에 따라 첫째 항이 결정되고,
①에 따라 제 2항이 결정되고, 다시 ①에 따라 제 3항이 결정되고..., 이것을 반복함으로써 일반항 an이 결정됩니다.
이렇게 수열을 결정하는 방법을 귀납적 정의라고 하며, 항 사이의 관계를 나타낸 ①과 ②를 점화식이라고 합니다.
문제 이해
하노이의 탑 문제의 목적은 A, B, C 세 장소가 있는 상황에서
n개의 원반이 큰 원반부터 작은 원반의 순서로 A라는 장소에 쌓여 있을 때,
1. 한 번에 한 개의 원판만 옮길 수 있다.
2. 가장 위에 있는 원판만 이동할 수 있다.
3. 큰 원판이 작은 원판 위에 있어서는 안 된다.
이 규칙에 따라 장소 A에 있는 모든 원반을 장소 C(또는 B)로 이동시키는 데 필요한 최소 이동 횟수를 구하는 것입니다.
문제 해결
n개의 원반이 쌓여 있을 때 이것을 앞의 규칙에 따라 다른 장소로 이동시키는 데 필요한 최소 이동 횟수를 an이라고 하면,
n개 전부를 장소 A에서 장소 C로 이동시키기 위해서는 다음과 같이 생각해 볼 수 있습니다.
(1) 장소 A에 있는 원반 n-1개를 장소 B에 이동시키는 최소 횟수는 an-1입니다.
(2) 장소 A에 남아 있는 한 개의 원반을 장소 C로 이동시키는 횟수는 1회입니다.
(3) 장소 B에 있는 n-1개의 원반을 장소 C에 이동시키는 최소 횟수는 an-1입니다.
이때 (1), (2), (3)에 따라 점화식 an = an-1 + 1 + an-1 = 2an-1 + 1을 얻을 수 있고,
이는 an+1 = 2an + 1로 고쳐 쓸 수 있습니다.
이것은 점화식 an+1 = pan + q에서 p = 2, q = 1인 경우이고, a1 = 1이므로 이 점화식의 일반항은 an = 2n - 1이 됩니다.